package cn.shenzz.suixiang.dp.leetcode_416;

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0, n = nums.length;
        for (int num : nums) sum += num;

        if ((sum & 1) == 1) return false;

        int target = sum >> 1;
        int[] dp = new int[target + 1];

        for (int num : nums) {
            for (int j = target; j >= num; --j) {
                dp[j] = Math.max(dp[j], dp[j - num] + num);
            }
        }

        return dp[target] == target;
    }
}